//
// Created by shenbin on 2022/4/21.
// https://leetcode.cn/problems/walking-robot-simulation/
//

#ifndef ALGORITHM_TRAINNING_C03_LC874_H
#define ALGORITHM_TRAINNING_C03_LC874_H

#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <string>

using namespace std;

/**
 * 关键：判断一个格子是不是障碍物，存和找
 * 存：用无序集合存储，找：哈希
 * 1. 存哈希，对障碍物的坐标做哈希存储，二维坐标转换一维数组，行号*列数+列号；
 * 2. 方向，news
 * 3. 方向数组， dx，dy
 */
class LeetCode874 {
public:
    int robotSim(vector<int> &commands, vector<vector<int>> &obstacles) {
        unordered_set<long long > obs;
        for (const vector<int> &obstacle: obstacles) {
            obs.insert(calcHash(obstacle));
        }
        int x = 0, y = 0, ans = 0;
        int dir = 0; // N=0, E=1, S=2, W=3
        // (dir+1) %4 右转
        // (dir+3) %4 左转
        //网格中行走题目，技巧：方向数组；
        const int dx[4] = {0, 1, 0, -1};// 向北走，x+0
        const int dy[4] = {1, 0, -1, 0};
        // command: -1 右转90度，-2 左转90度，1~9 向前移动 command 个单位
        for (int command: commands) {
            if (command == -1) {
                dir = (dir + 1) % 4;
            } else if (command == -2) {
                dir = (dir + 3) % 4;
            } else {
                for (int i = 0; i < command; i++) {
                    int nx = x + dx[dir];
                    int xy = y + dy[dir];
                    // 如果是障碍物
                    if (obs.find(calcHash({nx, ny})) != obs.end()) {
                        break;
                    }
                    x = nx, y = ny;
                    ans = max(ans, x * x + y * y);
                }
            }
        }

    }

private:
    /*
    string calcHash(const vector<int> &obstacle) {
        return to_string(obstacle[0]) + "," + to_string(obstacle[1]);
        //return obs[0] * 60001 + obs[1];
    }
    */
    long long  calcHash(const vector<int> &obstacle)
    {
        return (obstacle[0] + 30000) * 60001ll + (obstacle[1] + 30000);
    }
};

#endif //ALGORITHM_TRAINNING_C03_LC874_H
